#include <stdio.h>
#include <stdlib.h>
#include <windows.h>
#define maxsize 100

typedef struct {
	int key;
	// low表示此块最低位，high表示最高位
	int low, high;
}indexElem;

/*
	函数：indexSearch
	参数：index[]: 索引表数组; indexLength: 索引表数组长度; data[]: 待查询的数据数组; key: 需要检索的关键字
	返回值：int: 0表示没有查到,查到返回对应数组下标
	作用：分块查找数据
*/
int indexSearch(indexElem index[], int indexLength, int data[], int key) {
	int low, high, mid;
	low = 0, high = indexLength-1;

	while(low < high) {
		mid = (low + high) / 2;
		// 注意这里是=，对比折半插入排序是不同的，因为此处相同表示就应该在mid处查找，即hight+1处查找
		if(index[mid].key >= key) {
			high = mid -1;
		} else {
			low = mid + 1;
		}
	}

	int i = index[high].low;
	while(i <= index[high].high) {
		if(data[i] == key) {
			return i;
		}
		i++;
	}

	return 0;
}

int main() {
	system("chcp 65001 > nul");

	int data[18] = {22,12,13,8,9,20,33,42,44,38,24,48,60,58,74,49,86,53};
	int length = 18;
	int key=12;
	int indexLength = 3;
	
	//建立索引
	indexElem index[maxsize] = {{22,0,5},{48,6,11},{86,12,17}};

	int j = indexSearch(index, indexLength, data, key);

	if(j == 0) {
		printf("Failure!");
	} else {
		printf("%d is %dth number", data[j], j+1);
	}

	system("pause");
	return 0;
}